package main;

public class Matrix {
	public static float[][] inv(float a[][]) {
		int n = a.length;
		float x[][] = new float[n][n];
		float b[][] = new float[n][n];
		int index[] = new int[n];
		for (int i = 0; i < n; ++i) {
			b[i][i] = 1;
		}
		gaussian(a, index);
		for (int i = 0; i < n - 1; ++i) {
			for (int j = i + 1; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					b[index[j]][k] -= a[index[j]][i] * b[index[i]][k];
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			x[n - 1][i] = b[index[n - 1]][i] / a[index[n - 1]][n - 1];
			for (int j = n - 2; j >= 0; --j) {
				x[j][i] = b[index[j]][i];
				for (int k = j + 1; k < n; ++k) {
					x[j][i] -= a[index[j]][k] * x[k][i];
				}
				x[j][i] /= a[index[j]][j];
			}
		}
		return x;
	}

	public static void gaussian(float a[][], int index[]) {
		int n = index.length;
		float c[] = new float[n];
		for (int i = 0; i < n; ++i) {
			index[i] = i;
		}
		for (int i = 0; i < n; ++i) {
			float c1 = 0;
			for (int j = 0; j < n; ++j) {
				float c0 = Math.abs(a[i][j]);
				if (c0 > c1) {
					c1 = c0;
				}
			}
			c[i] = c1;
		}
		int k = 0;
		for (int j = 0; j < n - 1; ++j) {
			float pi1 = 0;
			for (int i = j; i < n; ++i) {
				float pi0 = Math.abs(a[index[i]][j]);
				pi0 /= c[index[i]];
				if (pi0 > pi1) {
					pi1 = pi0;
					k = i;
				}
			}
			int itmp = index[j];
			index[j] = index[k];
			index[k] = itmp;
			for (int i = j + 1; i < n; ++i) {
				float pj = a[index[i]][j] / a[index[j]][j];
				a[index[i]][j] = pj;
				for (int l = j + 1; l < n; ++l) {
					a[index[i]][l] -= pj * a[index[j]][l];
				}
			}
		}
	}
	
	public static float[] multi(float M1[][], float M2[]) {
		if (M1[0].length != M2.length) {
			return null;
		}
		float R[] = new float[M1.length];
		for (int i = 0; i < M1.length; i++) {
			for (int j = 0; j < M2.length; j++) {
				R[i] += M1[i][j] * M2[j];
			}
		}
		return R;
	}
	

	public static float[] solve(float[][] A, float[] b) {
		if (A.length != A[0].length)
			return null;
		float[][] invA = inv(A);
		if (invA == null)
			return null;
		return multi(invA, b);
	}

}
